POI2013 Inspector

POI
二分, 想法

POI2013 Inspector

题目大意：

一天公司有n个员工和m个员工记录，每个员工只会在连续的一段时间内工作。当然写观察记录的时候肯定会在工作。记录会给出当时除了他还有多少人在公司。现在给出m条记录分别是谁写的、什么时候写的以及写的时候还有多少人。求第k条记录使得前k条记录可以同时存在不矛盾，且前k+1条记录是矛盾的。输出这个k。

$PS.$ 没有写出来，但似乎并不难。有些乱，但似乎只是乱搞就可以AC？
最后还是去看了题解，在这里orz commoc，他的题解写的很好。

commoc的题解戳这儿

题解：

一个很明显的思路是二分答案，把题目转化成判定性的问题，这样记录就没有先后顺序之分了。

重点是有关出现矛盾的判断:

  1. 记录本身的矛盾：两个记录在同一时刻，但人数不同。

    这个可以直接特判，比较无脑。

  2. 记录的记载而产生约束关系形成了矛盾：比如某人在L时刻、R时刻都记录了东西，但L、R之间存在别人的一个记录，说除他外没有人了，这显然就有问题了。因为刚开始的那个人，在[L,R]之间是必然一直存在的。

    这个也比较容易判断：

    我们记录每一个人的最晚开始时间与最早结束时间，当成一条线段。对于每一个时间点，我们看看有多少条线段覆盖它。(这是当前时刻最少工作人数)

    如果它大于当前时间点的记录人数，显然不可行。

  3. 可以构造出方案，但会超过n个人的限制。

    这与上一条的区别在于它是可以满足约束条件的，但人数会超。

    比如：1时刻有一个人记录有两个人，2时刻记录有1个人，3时刻记录有2个人。当n=3时显然是可以的，但n=2时显然不行。

    首先我们想到，人数少是无所谓的，可以认为有些人一直未工作或不在记录的时间点上工作。

    所以我们只要算出符合条件的最少人数，看是否小于等于n即可。

    那么如何计算呢？

    令now表示当前必须在工作的人的数量，total表示当前最少符合的人数。

    并令done表示所对应区间已经过去了，还可以留下来工作的人。

    令notbegin表示所对应的区间已经过去，但还可以留下来工作的人。

    每到达一个新的时刻，我们可以比较一下now+done+notbegin与tot[i] (这个点记录的人数) 的大小。

    如果比tot[i] 小，说明人数还不够，我们需要再让一些人提前开始工作。

    如果比tot[i] 大，那说明人数多了，我们就让done中的人结束工作，如果还是多，那就让notbegin中的人结束工作。

    这时可能会有一个问题：

    notbegin的区间还没有开始，怎么可以结束工作呢？这样不相当于矛盾了么?

    其实并不是，我们可以认为，我们去掉的是一个没有写过记录的人，他们没有记录，因而没有固定的区间，他们可以随时开始随时结束。(但他们也会被记录到total中)

这样一来，题目即可解决了。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=(int)1e5+1,inf=(int)1e9+7;
int n,m,t[N],id[N],num[N],tot[N];
int st[N],ed[N],mi[N],mx[N];
bool judge(int lim){
	for(int i=1;i<=n;i++)
		mi[i]=inf,mx[i]=-inf;
	for(int i=1;i<=m;i++)
		tot[i]=st[i]=ed[i]=0;
	for(int i=1;i<=lim;i++){
		if(tot[t[i]]&&tot[t[i]]!=num[i]+1)return false;
		tot[t[i]]=num[i]+1;
		mi[id[i]]=min(mi[id[i]],t[i]);
		mx[id[i]]=max(mx[id[i]],t[i]);
	}
	for(int i=1;i<=n;i++)
		if(mi[i]!=inf&&mx[i]!=-inf)
			st[mi[i]]++,ed[mx[i]]++;
	int now=0,total=0,notbegin=0,done=0;
	for(int i=1;i<=m;i++){
		if(tot[i]){
			now+=st[i];
			if(now>tot[i])return false;
			notbegin-=st[i];
			if(notbegin<0)total-=notbegin,notbegin=0;
			if(now+notbegin+done<tot[i])total+=tot[i]-now-notbegin-done,notbegin=tot[i]-done-now;
			else{
				if(now+notbegin<=tot[i])done=tot[i]-notbegin-now;
				else notbegin=tot[i]-now,done=0;
			}
			now-=ed[i],done+=ed[i];
		}
	}   
    if(total>n)return false;
	return true;
}
void solve(){
	Rd(n),Rd(m);
	for(int i=1;i<=m;i++)
		Rd(t[i]),Rd(id[i]),Rd(num[i]);
	int L=0,R=m,res=0;
	while(L<=R){
		int mid=L+R>>1;
		if(judge(mid)){
			res=mid;
			L=mid+1;
		}else R=mid-1;
	}
	printf("%d\n",res);
}
int main(){
	int cas;Rd(cas);
	for(;cas--;)solve();
	return 0;
}
分享到 评论